Longest line of consecutive one in matrix

Time: O(MxN); Space: O(N); medium

Given a (0,1) matrix, find the longest line of consecutive 1 in the matrix.

The line could be horizontal, vertical, diagonal or anti-diagonal.

Example 1:

Input: A =

[
    [0,1,1,0],
    [0,1,1,0],
    [0,0,0,1]
]

Output: 3

Explanation:

  • (0,1) (1,2) (2,3)

Example 2:

Input: A =

[
    [0,0],
    [1,1]
]

Output: 2

Constraints:

  • The number of elements in the given matrix will not exceed 10,000.

[1]:

class Solution1(object):
    """
    Time: O(M*N)
    Space: O(N)
    """
    def longestLine(self, M):
        """
        :type M: List[List[int]]
        :rtype: int
        """
        if not M: return 0
        result = 0

        dp = [[[0] * 4 for _ in range(len(M[0]))] for _ in range(2)]

        for i in range(len(M)):
            for j in range(len(M[0])):
                dp[i % 2][j][:] = [0] * 4
                if M[i][j] == 1:
                    dp[i % 2][j][0] = dp[i % 2][j - 1][0]+1 if j > 0 else 1
                    dp[i % 2][j][1] = dp[(i-1) % 2][j][1]+1 if i > 0 else 1
                    dp[i % 2][j][2] = dp[(i-1) % 2][j-1][2]+1 if (i > 0 and j > 0) else 1
                    dp[i % 2][j][3] = dp[(i-1) % 2][j+1][3]+1 if (i > 0 and j < len(M[0])-1) else 1
                    result = max(result, max(dp[i % 2][j]))

        return result

[2]:

s = Solution1()

M = [
  [0,1,1,0],
  [0,1,1,0],
  [0,0,0,1]
]
assert s.longestLine(M) == 3

M = [
  [0,0],
  [1,1]
]
assert s.longestLine(M) == 2